package Leetcode.DayTest;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * @Author: kirito
 * @Date: 2024/5/25 13:38
 * @Description:
 * 找出满足差值条件的下标 I
 * 简单
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。
 *
 * 你的任务是从范围 [0, n - 1] 内找出  2 个满足下述所有条件的下标 i 和 j ：
 *
 * abs(i - j) >= indexDifference 且
 * abs(nums[i] - nums[j]) >= valueDifference
 * 返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。
 *
 * 注意：i 和 j 可能 相等 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
 * 输出：[0,3]
 * 解释：在示例中，可以选择 i = 0 和 j = 3 。
 * abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
 * 因此，[0,3] 是一个符合题目要求的答案。
 * [3,0] 也是符合题目要求的答案。
 * 示例 2：
 *
 * 输入：nums = [2,1], indexDifference = 0, valueDifference = 0
 * 输出：[0,0]
 * 解释：
 * 在示例中，可以选择 i = 0 和 j = 0 。
 * abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。
 * 因此，[0,0] 是一个符合题目要求的答案。
 * [0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。
 * 示例 3：
 *
 * 输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
 * 输出：[-1,-1]
 * 解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
 * 因此，返回 [-1,-1] 。
 */

public class findIndices {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (j - i >= indexDifference && Math.abs(nums[j] - nums[i]) >= valueDifference) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};

    }

    public int[] findIndices2(int[] nums, int indexDifference, int valueDifference) {
        int maxIdx = 0;
        int minIdx = 0;
        for (int j = indexDifference; j < nums.length; j++) {
            int i = j - indexDifference;
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            } else if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
            if (nums[maxIdx] - nums[j] >= valueDifference) {
                return new int[]{maxIdx, j};
            }
            if (nums[j] - nums[minIdx] >= valueDifference) {
                return new int[]{minIdx, j};
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 给你两个整数数组 nums1 和 nums2。
     *
     * 从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
     *
     * 执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
     *
     * 返回能够实现数组相等的 最小 整数 x 。
     *
     *
     * 示例 1:
     *
     * 输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]
     *
     * 输出：-2
     *
     * 解释：
     *
     * 移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。
     *
     * 示例 2:
     *
     * 输入：nums1 = [3,5,5,3], nums2 = [7,7]
     *
     * 输出：2
     *
     * 解释：
     *
     * 移除 nums1 中下标为 [0,3] 的两个元素，并且每个元素与 2 相加后，nums1 变为 [7,7] ，与 nums2 相等。
     * int cmp(const void *a, const void *b) {
     *     return *(int*)a - *(int*)b;
     * }
     *
     * int minimumAddedInteger(int* nums1, int nums1Size, int* nums2, int nums2Size) {
     *     qsort(nums1, nums1Size, sizeof(int), cmp);
     *     qsort(nums2, nums2Size, sizeof(int), cmp);
     *     // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
     *     // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
     *     for (int i = 2; i > 0; i--) {
     *         int x = nums2[0] - nums1[i];
     *         // 在 {nums1[i] + x} 中找子序列 nums2
     *         int j = 0;
     *         for (int k = i; k < nums1Size; k++) {
     *             if (nums2[j] == nums1[k] + x && ++j == nums2Size) {
     *                 // nums2 是 {nums1[i] + x} 的子序列
     *                 return x;
     *             }
     *         }
     *     }
     *     // 题目保证答案一定存在
     *     return nums2[0] - nums1[0];
     * }
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
        // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
        for (int i = 2; i > 0; i--) {
            int x = nums2[0] - nums1[i];
            // 在 {nums1[i] + x} 中找子序列 nums2
            int j = 0;
            for (int k = i; k < nums1.length; k++) {
                if (nums2[j] == nums1[k] + x && ++j == nums2.length) {
                    // nums2 是 {nums1[i] + x} 的子序列
                    return x;
                }
            }
        }
        // 题目保证答案一定存在
        return nums2[0] - nums1[0];
    }

    public static int findGCD(int[] nums) {
        int len = nums.length;
        int min=nums[0];
        int max =nums[0];
        for (int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        return gcd(min,max);
    }
    /**
     * 最大公约数
     * @param m
     * @param n
     * @return
     */
    public static int Euclid(int m,int n){
        int r;

        while (n != 0) {
            r = m % n;
            m = n;
            n = r;
        }
        return m;
    }
    //递归
    public static  int gcd(int m, int n){
        if(n == 0){
            return m;
        }
        return gcd(n, m % n);
    }

    /**
     * 有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
     *
     * 给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
     *
     * 每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到  队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
     *
     * 返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
     *
     * 示例 1：
     *
     * 输入：tickets = [2,3,2], k = 2
     * 输出：6
     * 解释：
     *
     * 队伍一开始为 [2,3,2]，第 k 个人以下划线标识。
     * 在最前面的人买完票后，队伍在第 1 秒变成 [3,2,1]。
     * 继续这个过程，队伍在第 2 秒变为[2,1,2]。
     * 继续这个过程，队伍在第 3 秒变为[1,2,1]。
     * 继续这个过程，队伍在第 4 秒变为[2,1]。
     * 继续这个过程，队伍在第 5 秒变为[1,1]。
     * 继续这个过程，队伍在第 6 秒变为[1]。第 k 个人完成买票，所以返回 6。
     *
     * n == tickets.length
     * 1 <= n <= 100
     * 1 <= tickets[i] <= 100
     * 0 <= k < n
     * 思路1：模拟
     * 思路2：想一想，当第k个人完成买票的那一刻，在他前后的人，分别买了多少票?
     * 假设第 k个人此时买了3张票，那么排在他前面的人，此时也至多买了3张票;排在他后面的人，此时
     * 至多买了 2张票。
     * 把 tickets 简记为 t。一般地，当第 k 个人买了 tk 张票时:
     * 排在他前面的人，
     * ，买的票不会超过 tk，即 min(ti,tk)。
     * 买的票不会超过 tk-1，即 min(ti,t -1)。
     * 排在他后面的人，
     * 累加所有购票数即为答案
     */
    public int timeRequiredToBuy_imitate(int[] tickets, int k) {
        int ans = 0;
        int n = tickets.length;
        Queue<int[]> que = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            que.add(new int[]{tickets[i], i});
        }
        while (!que.isEmpty()) {
            ans++;
            int[] poll = que.poll();
            poll[0]--;
            if (poll[1] == k && poll[0] == 0) {
                break;
            }
            if (poll[0] > 0) {
                que.add(poll);
            }

        }
        return ans;
    }
    public int timeRequiredToBuy(int[] tickets, int k) {
        int ans = 0;
        int tk = tickets[k];
        for (int i = 0; i < tickets.length; i++) {
            ans += Math.min(tickets[i], (i <= k ? tk : tk - 1));
        }
        return ans;
    }

    public static void main(String[] args) {
//        System.out.println(Euclid(24,60));
//        System.out.println(gcd(24,60));
        int[] nums = {2,5,6,9,10};
        System.out.println(findGCD(nums));
    }
}
